#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define EMPTY_CELL (0)
#define LENGTH     (9)
#define TIMEOUT    (100000)


int is_num_even(int num)
{
    if(num%2 == 0) return 1;
    return 0;
}

int random_number(int min_num, int max_num)
{
    int result = 0, low_num = 0, hi_num = 0;

    if (min_num < max_num)
    {
        low_num = min_num;
        hi_num = max_num + 1; // include max_num in output
    }
    else
    {
        low_num = max_num + 1; // include max_num in output
        hi_num = min_num;
    }

    result = (rand() % (hi_num - low_num)) + low_num;

    return result;
}


int random_number2(int min_num, int max_num)
{
    static int rand_num = 1;
    rand_num++;
    if(rand_num > max_num) rand_num = 1;
    return rand_num;
}

int is_in_arr(int num, int *arr, int len)
{
    for(int i = 0; i < len; i++)
    {
        if(num == arr[i])
        {
            return 1;
        }
    }
    return 0;
}

int rand_gen(int *obj_arr, int gen_type, int len)
{
    long timeout = TIMEOUT;
    while(--timeout)
    {
        int num = 0;
        if(gen_type == 1)
        {
            num = random_number(1, len);
        }
        else
        {
            num = random_number2(1, len);
        }
        if(!is_in_arr(num, obj_arr, len))
        {
            return num;
        }
    }
    if(timeout == 0)
    {
        printf("[rand_gen] timeout! \n");
        return 0;
    }
}


void num_init(int (*arr)[LENGTH], int len)
{
    for(int i = 0; i < len; i++)
    {
        for(int j = 0; j < len; j++)
        {
            arr[i][j] = EMPTY_CELL;
        }
    }
}

void get_cur_row(int (*arr)[LENGTH], int *row, int row_idx, int len)
{
    for(int c = 0; c < len; c++)
    {
        row[c] = arr[row_idx][c];
    }
}

void get_cur_col(int (*arr)[LENGTH], int *col, int col_idx, int len)
{
    for(int r = 0; r < len; r++)
    {
        col[r] = arr[r][col_idx];
    }
}

void get_cur_group(int (*arr)[LENGTH], int *group, int row_idx, int col_idx, int len)
{
    int grp_idx = 0;
    int row_st;
    int col_st;
    int cut;
    if(len == 4)
    {
        cut = 2;
    }
    else
    {
        cut = 3;
    }

    row_st = row_idx / cut * cut;
    col_st = col_idx / cut * cut;

    //printf("[row_st=%d, col_st=%d]", row_st, col_st);

    for(int r = row_st; r < row_st+cut; r++)
    {
        for(int c = col_st; c < col_st+cut; c++)
        {
            group[grp_idx++] = arr[r][c];
        }
    }
}

void random_sudoku_gen(int (*psudoku)[LENGTH])
{
    int cur_row[LENGTH] = {0};
    int cur_col[LENGTH] = {0};
    int cur_group[LENGTH] = {0};
    long timeout = TIMEOUT;

    for(int r = 0 ; r < LENGTH; r++)
    {
        for(int c = 0; c < LENGTH; c++)
        {
            get_cur_row(psudoku, cur_row, r, LENGTH);
            get_cur_col(psudoku, cur_col, c, LENGTH);
            get_cur_group(psudoku, cur_group, r, c, LENGTH);

            int rand_num = 0;
            while(--timeout)
            {
                rand_num = rand_gen(cur_row, 2, LENGTH);
                if(!is_in_arr(rand_num, cur_col, LENGTH))
                {
                    if(!is_in_arr(rand_num, cur_group, LENGTH))
                    {
                        break;
                    }
                }
            }
            if(timeout == 0)
            {
                timeout = TIMEOUT;
                while(--timeout)
                {
                    rand_num = rand_gen(cur_row, 2, LENGTH);
                    if(!is_in_arr(rand_num, cur_col, LENGTH))
                    {
                        if(!is_in_arr(rand_num, cur_group, LENGTH))
                        {
                            break;
                        }
                    }
                }
                if(timeout == 0)
                {
                    printf("[random_sudoku_gen] timeout! \n");
                    return;
                }
            }

            psudoku[r][c] = rand_num;
            printf("%d ", rand_num);
        }
        printf("\n");
    }

}

int main()
{
    int sudoku[LENGTH][LENGTH];

    num_init(sudoku, LENGTH);

    srand(time(NULL));

    printf("Sudoku Generate:\n");

    random_sudoku_gen(sudoku);

    return 0;
}
